A color digital image is typically displayed or printed in the form of a rectangular array of pixels. A color digital image may be represented in a computer by three arrays of binary numbers. Each array represents an axis of a suitable color coordinate system. The color of a pixel in the digital image is defined by an associated binary number, which defines one of three color components from the color coordinate system, from each array. There are many color coordinate systems that are often used to represent the color of a pixel. These color coordinate systems include a “Red-Green-Blue” (RGB) coordinate system and a cyan-magenta-yellow (CMY) coordinate system. The RGB coordinate system is commonly used in monitor display applications and the CMY coordinate system is commonly used in printing applications.
The amount of data used to represent a digital image is extremely large, which often results in significant costs that are associated both with increased storage capacity requirements, and the computing resources and time required to transmit the data to another computing device. Efforts to reduce these costs through digital image compression techniques, such as, color quantization, have been developed. Color quantization of an image is a process in which the bit-depth of a source color image is reduced. Extreme color quantization is a process in which the bit-depth of a source color image is severely reduced, such as, from millions of colors to dozens of colors.
Extreme color quantization has also been used for region segmentation and non-photographic rendering, where a significantly reduced bit-depth is desirable. For instance, extreme color quantization has been used to combine multiple sets of colors into single colors. One application of extreme color quantization is to render a photographic color digital image to have a “cartoon-like” appearance.
There are two main challenges to implementing extreme color quantization. The first challenge involves identifying the locations of the nodes to which the colors are mapped in a representation. The second challenge involves identifying the shapes of the boundaries that define the range of input colors to be mapped to the respective single output colors. Ideally, the nodes and their boundaries are consistent with those nodes and boundaries that are likely to be used by a human observer. By way of example, a node may be a location for a “gray” color and the boundary of that node may be all of the colors that are “grayish”.
However, conventional color quantization, particularly extreme color quantization, processes are unable to meet or come close to the ideal conditions. For instance, the resulting nodes of the quantization often fall relatively far away from the colors or hues that a human observer would likely select as being optimal. In addition, the resulting uniform boundaries for the different color regions do not accurately follow their corresponding nodes.
An example of a representation resulting from application of a conventional extreme quantization process on a color digital image is depicted in the diagram 100 shown in FIG. 1. The diagram 100, more particularly, depicts the nodes 102-108 resulting from a conventional extreme quantization process. In addition, the x-axis or a* axis denotes the redness-greenness, the y-axis or b* axis denotes the yellowness-blueness, and the z-axis denotes the lightness axis, which goes through an origin of the diagram 100, of the colors processed in the CIELAB color space.
In FIG. 1, the node 102 denotes the location of the color that is close to pure or ideal green, the node 104 denotes the location of the color that is close to pure or ideal yellow, the node 106 denotes the location of the color that is close to pure or ideal red, and the node 108 denotes the location of the color that is close to pure or ideal blue. As shown in FIG. 1, the nodes 102-108 are relatively far from the negative a* axis 126, the positive b* axis 124, the positive a* axis, and the negative b* axis, respectively. The diagram 100 thus illustrates that the resulting locations of the colors, as denoted by the nodes 102-106, are relatively far from the colors that a human observer would likely select as being ideal.
Another example of a representation resulting from application of a conventional extreme quantization process on a color digital image is depicted in the diagram 200 of FIG. 2. Similarly to FIG. 1, the diagram 200 depicts the nodes 102-108 resulting from a conventional extreme quantization process. In addition, the same data plotted in FIG. 1 has been plotted in FIG. 2, which denotes a conventional YCC color space. As such, the x-axis or C2 axis denotes the redness-greenness, the y-axis or C1 axis denotes the yellowness-blueness, and the z-axis denotes the luminance axis, which goes through an origin of the diagram 200, of the colors processed in a conventional YCC color space.
As in FIG. 1, the node 102 denotes the location of the color that is close to pure or ideal green, the node 104 denotes the location of the color that is close to pure or ideal yellow, the node 106 denotes the location of the color that is close to pure or ideal red, and the node 108 denotes the location of the color that is close to pure or ideal blue. Again, the nodes 102-108 are illustrated as being relatively far from the negative c1 axis 130, the positive c2 axis 132, the positive c1 axis, and the negative c2 axis, respectively. The diagram 200 thus illustrates that the resulting locations of the colors, as denoted by the nodes 102-106, are relatively far from the colors that a human observer would likely select as being ideal.
Although not shown in FIGS. 1 and 2, uniform boundaries for the different regions in the diagrams 100 and 200 do not accurately follow their corresponding nodes 102-108 because, as denoted by the lines 112-118 connecting the nodes 102-108 to a center of the diagrams 100 and 200, opposing lines are not orthogonal with respect to each other.
It would therefore be desirable to have a process for extreme color quantization that does not suffer from the drawbacks and disadvantages of convention color quantization techniques.